package com.tongtech.proxy.core.slices;

public class SkipList {
    private Node head;
    private int size;

    public SkipList() {
        this.head = new Node(Integer.MIN_VALUE);
        this.size = 0;
    }

    public void add(int key) {
        Node node = new Node(key);
        int level = randomLevel();
        node.forward = new Node[level + 1];

        Node current = head;
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].key < key) {
                current = current.forward[i];
            }
            node.forward[i] = current.forward[i];
            current.forward[i] = node;
        }

        size++;
    }

    private int randomLevel() {
        return 0;
    }

    public boolean contains(int key) {
        Node current = head;
        for (int i = level(); i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].key < key) {
                current = current.forward[i];
            }
        }
        return current.forward[0] != null && current.forward[0].key == key;
    }

    public void remove(int key) {
        Node current = head;
        Node[] prev = new Node[level() + 1];
        for (int i = level(); i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].key < key) {
                current = current.forward[i];
            }
            prev[i] = current;
        }

        if (current.forward[0] != null && current.forward[0].key == key) {
            for (int i = level(); i >= 0; i--) {
                if (prev[i].forward[i] == current) {
                    prev[i].forward[i] = current.forward[i];
                }
            }
            size--;
        }
    }

    public int size() {
        return size;
    }

    private int level() {
        int level = 0;
        while (Math.random() < 0.5) {
            level++;
        }
        return level;
    }

    private static class Node {

        int key;
        Node[] forward;

        public Node(int key) {
            this.key = key;
        }
    }
}
